\section {A time-shared computer system}
\label {sec:timeshared}

This example is adapted from \cite{sLAW00a}, Section~2.4.
Consider a simplified time-shared computer system comprised of $T$
identical and independent terminals, all busy, using a common server
(e.g., for database requests, or central processing unit (CPU) 
consumption, etc.).
Each terminal user sends a task to the server at some random time and
waits for the response.  After receiving the response, he thinks
for some random time before submitting a new task, and so on.

We assume that the thinking time is an exponential  random variable 
with mean $\mu$, whereas the server's time needed for a request is a
Weibull random variable with parameters $\alpha$, $\lambda$ and $\delta$.
The tasks waiting for the server form a single queue with a 
{\em round robin\/} service policy with {\em quantum size\/} $q$,
which operates as follows.
When a task obtains the server, if it can be completed in less than $q$ 
seconds, then it keeps the server until completion.
Otherwise, it gets the server for $q$ seconds and returns to the back
of the queue to be continued later.
In both cases, there is also $h$ additional seconds of {\em overhead\/}
for changing the task that has the server's attention.


\unitlength=1in
\begin{picture}(6.0, 2.9)(0.0,0.3)
\thicklines\bf
\put(1.5,1.0){\circle{0.4}}
\put(1.5,1.5){\circle{0.4}}
\put(1.5,2.5){\circle{0.4}}
\put(1.5,1.0){\makebox(0,0){1}}
\put(1.5,1.5){\makebox(0,0){2}}
\put(1.5,2.5){\makebox(0,0){T}}
\multiput(1.5,1.85)(0.0,0.15){3}{\circle*{0.05}}
\put(3.9,1.7){\framebox(0.8,0.4){CPU}}
\multiput(3.5,1.75)(0.1,0.0){4}{\line(0,1){0.3}}
\put(1.1,1.2){\line(0,1){1.1}}
\put(1.9,1.2){\line(0,1){1.1}}
\put(0.7,2.2){\line(0,1){0.5}}
\put(0.9,2.0){\vector(1,0){0.2}}
\put(1.9,2.0){\vector(1,0){1.5}}
\put(3.0,1.8){\vector(1,0){0.4}}
\put(3.0,1.4){\line(1,0){2.1}}
\put(4.7,1.9){\line(1,0){0.4}}
\put(0.9,2.9){\line(1,0){4.2}}
\put(1.3,1.2){\oval(0.4,0.4)[bl]}
\put(1.3,1.7){\oval(0.4,0.4)[bl]}
\put(1.3,2.3){\oval(0.4,0.4)[tl]}
\put(1.7,2.3){\oval(0.4,0.4)[tr]}
\put(1.7,1.7){\oval(0.4,0.4)[br]}
\put(1.7,1.2){\oval(0.4,0.4)[br]}
\put(0.9,2.2){\oval(0.4,0.4)[bl]}
\put(0.9,2.7){\oval(0.4,0.4)[tl]}
\put(3.0,1.6){\oval(0.4,0.4)[l]}
\put(5.1,1.65){\oval(0.4,0.5)[r]}
\put(5.1,2.4){\oval(0.4,1.0)[r]}
\small\rm
\put(1.5,0.65){\makebox(0,0){Terminals}}
\put(4.1,1.25){\makebox(0,0){End of quantum}}
\put(3.2,2.75){\makebox(0,0){End of task}}
\put(3.65,2.2){\makebox(0,0){Waiting queue}}
\end{picture}


The {\em response time\/} of a task is defined as the difference
between the time when the task ends (including the overhead $h$ at the
end) and the arrival time of the task to the server.
We are interested in the {\em mean response time}, in steady-state.
We will simulate the system until $N$ tasks have ended, with all
terminals initially in the ``thinking'' state.
To reduce the initial bias, we will start collecting statistics only
after $N_0$ tasks have ended (so the first $N_0$ response times are
not counted by our estimator, and we take the average response
time for the $N-N_0$ response times that remain).
This entire simulation is repeated $R$ times, independently,
so we can estimate the variance of our estimator.
% and compute a confidence interval for the true mean response time.


Suppose we want to compare the mean response times for two 
different configurations of this system, where a configuration is
characterized by the vector of parameters $(T, q, h, \mu, \alpha, \lambda, \delta)$.
We will make $R$ independent simulation runs (replications)
for each configuration.
To compare the two configurations, we want to use {\em common random
numbers}, i.e., the same streams of random numbers 
across the two configurations.
We couple the simulation runs by pairs: 
for run number $i$, let $R_{1i}$ and $R_{2i}$ be the mean response times 
for configurations 1 and 2, and let
      $$D_i = R_{1i} - R_{2i}.$$
We use the same random numbers to obtain $R_{1i}$ and $R_{2i}$,
for each $i$.
The $D_i$ are nevertheless independent random variables (under the blunt
assumption that the random streams really produce independent uniform
random variables) and we can use them to compute a confidence interval
for the difference $d$ between the theoretical mean response times of the
two systems.
Using common random numbers across $R_{1i}$ and $R_{2i}$ should reduce
the variance of the $D_i$ and the size of the confidence interval.

\bigskip
\lstinputlisting[label=lst:TimeShared,caption={Simulation of a time shared system}]{TimeShared.java}

The program of Listing~\ref{lst:TimeShared} performs this simulation.
In \texttt{TimeShared}, the variable \texttt{conf} indicates the current
configuration number.  For each configuration, 
% we read the configuration data and 
we make \texttt{nbRep} simulation runs.
The array \texttt{meanConf1} memorizes the values of $R_{1i}$, and the
statistical probe \texttt{statDiff} collect the differences $D_i$, in
order to compute a confidence interval for $d$.
After all the runs for the first configuration have been completed,
the random number streams are reset to their initial seeds,
so that the two configurations get the same random numbers.
The random streams are also reset to the beginning of their next
substream after each run, to make sure that for the corresponding runs
for the two configurations, the generators start from exactly the same
seeds and generate the same numbers.

For each simulation run, the statistical probe \texttt{meanInRep}
is used to compute the average response time for the $N - N_0$ tasks
that terminate after the warm-up.
It is initialized before each run and updated with a new observation
at the $i$th task termination, for $i = N_0+1,\dots,N$.
At the beginning of a run, a \texttt{Terminal} process is activated for
each terminal.  When the $N$th task terminates, the corresponding
process invokes \texttt{Sim.stop} to stop the simulation and
to return the control to
the instruction that follows the call to \texttt{simulOneRun} in
\texttt{TimeShared}.

\setbox3=\vbox {\hsize = 6.0in
\begin{verbatim}
REPORT on Tally stat. collector ==> Differences on mean response times
   min          max        average      standard dev.   nb. obs.
   -0.134      0.369        0.168         0.175            10
 
        90.0 confidence interval for mean ( 0.067, 0.269 )
\end{verbatim}
}

\begin{figure}[ht]
\centerline{\boxit{\box3}}
\caption {Difference in the mean response times for $q=0.1$ and $q=0.2$ 
    for the time shared system.}
\label {fig:timeshared-res}
\end{figure}

For a concrete example, let $T=20$, $h=.001$, $\mu=5$ sec., $\alpha=1/2$,
$\lambda=1$ and $\delta=0$ for the two configurations.
With these parameters, the mean of the Weibull distribution is 2.
Take $q=0.1$ for configuration 1 and $q=0.2$ for configuration 2.
We also choose $N_0=100$, $N=1100$, and $R=10$ runs.
With these numbers in the data file, the program gives the results of
Figure~\ref{fig:timeshared-res}.
The confidence interval on the difference between the response time
with $q=0.1$ and that with $q=0.2$ contains only positive numbers.
We can therefore conclude that 
the mean response time is significantly shorter (statistically) 
with $q=0.2$ than with $q = 0.1$ (assuming that we can neglect the
bias due to the choice of the initial state).
To gain better confidence in this conclusion, we could repeat the 
simulation with larger values of $N_0$ and $N$.

Of course, the model could be made more realistic by considering,
for example, different types of terminals, with different parameters,
a number of terminals that changes with time,
different classes of tasks with priorities, etc.
SSJ offers the tools to implement these generalizations easily.
The program would be more elaborate but its structure would be similar.
